#ifndef SPTADT_H
#define SPTADT_H

namespace spt
{
	template<typename T>
	class ArrayBase
	{
	public:
		ArrayBase(T* Arr, uint32 Len)
		{
			arr = Arr;
			len = Len;
			lock.UnLock();
		}
	public:
		uint32 ArrLen() { return len; }
		T& operator[](uint32 index) { return arr[index]; }
	public:
		WRLock& Lock() { return lock; };
	protected:
		WRLock lock;
		T* arr;
		uint32 len;
	};
	template<typename T>
	class QueueBase:public ArrayBase<T>
	{
	public:
		QueueBase(T* Arr, uint32 Len):ArrayBase<T>::ArrayBase(Arr,Len)
		{
			Clear();
		}
		bool8 PushBack()
		{
			if (top > bottom)
			{
				top--;
				return 1;
			}
			return 0;
		}
		bool8 PushBack(T& Value)
		{
			if (top > bottom)
			{
				top--;
				Value = ArrayBase<T>::arr[top];
				return 1;
			}
			return 0;
		}
		bool8 Push(const T& Value) {
			if (top < ArrayBase<T>::ArrLen())
			{
				ArrayBase<T>::arr[top] = Value;
				top++;
				return 1;
			}
			return 0;
		}
		bool8 PopBack()
		{
			if (bottom > 0)
			{
				bottom--;
				return 1;
			}
			return 0;
		}
		bool8 PopBack(const T& Value)
		{
			if (bottom > 0)
			{
				bottom--;
				ArrayBase<T>::arr[bottom] = Value;
				return 1;
			}
			return 0;
		}
		bool8 Pop(T& Value)
		{
			if (bottom < top)
			{
				Value = ArrayBase<T>::arr[bottom];
				bottom++;
				return 1;
			}
			return 0;
		}
		uint32 Top() { return top; }
		uint32 Bottom() { return bottom; }
		
	public:
		void Clear() { top = bottom = 0; }
	public:
		uint32 top;
		uint32 bottom;
	};

	template<typename T>
	class RingBase :public ArrayBase<T>
	{
	public:
		RingBase(T* Arr, uint32 Len) :ArrayBase<T>::ArrayBase(Arr, Len)
		{
			Clear();
		}
		bool8 PushBack()
		{
			if (top != bottom)
			{
				top = (top - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				return 1;
			}
			else if (is_full)
			{
				top = (top - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				is_full = 0;
				return 1;
			}
			return 0;
		}
		bool8 PushBack(T& Value)
		{
			if (top != bottom)
			{
				top = (top - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				Value = ArrayBase<T>::arr[top];
				return 1;
			}
			else if (is_full)
			{
				is_full = 0;
				top = (top - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				Value = ArrayBase<T>::arr[top];
				return 1;
			}
			return 0;
		}
		bool8 Push(const T& Value) {

			ArrayBase<T>::arr[top] = Value;
			top = (top + 1) % ArrayBase<T>::len;
			if (top == bottom)
			{
				is_full = 1;
			}
			else
			{
				is_full = 0;
			}
			return 1;
		}
		bool8 PopBack()
		{
			if (top != bottom)
			{
				bottom = (bottom - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				return 1;
			}
			else if (is_full)
			{
				is_full = 0;
				bottom = (bottom - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				return 1;
			}
			return 0;
		}
		bool8 PopBack(const T& Value)
		{
			if (top != bottom)
			{
				bottom = (bottom - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				ArrayBase<T>::arr[bottom] = Value;
				return 1;
			}
			else if (is_full)
			{
				is_full = 0;
				bottom = (bottom - 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				ArrayBase<T>::arr[bottom] = Value;
				return 1;
			}
			return 0;
		}
		bool8 Pop(T& Value)
		{
			if (bottom != top)
			{
				Value = ArrayBase<T>::arr[bottom];
				bottom = (bottom + 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				return 1;
			}
			else if (is_full)
			{
				is_full = 0;
				Value = ArrayBase<T>::arr[bottom];
				bottom = (bottom + 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
				return 1;
			}
			return 0;
		}
		uint32 Top() { return top; }
		uint32 Bottom() { return bottom; }
	public:
		T& TopBuf() { return ArrayBase<T>::arr[top]; }
		void Push()
		{
			top = (top + 1) % ArrayBase<T>::len;
			if (top == bottom)
			{
				is_full = 1;
			}
			else
			{
				is_full = 0;
			}
		}
		T& BottomBuf() { return ArrayBase<T>::arr[bottom]; }
		void Pop()
		{
			if (bottom != top)
			{
				bottom = (bottom + 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
			}
			else if (is_full)
			{
				is_full = 0;
				bottom = (bottom + 1 + ArrayBase<T>::len) % ArrayBase<T>::len;
			}
		}
	public:
		void Clear() { top = bottom = is_full =0;}
		bool8 IsEmpty() { return (top == bottom)&&(!is_full); };
	public:
		bool8 is_full;
		uint32 top;
		uint32 bottom;
	};

	template<typename T>
	class SListItem
	{
	public:
		SListItem() { item = 0; next = 0; }
		SListItem(T* Item) { item = Item; next = 0; }
		SListItem(T* Item, SListItem*Next) { item = Item; next = Next; }
		T* Item() { return item; }
		T* Item(T* Item) { return item = Item; }
		SListItem* Next() { return next; }
		SListItem* Next(SListItem* Next) { return next=Next; }
	private:
		T* item;
		SListItem* next;
	};

	template<typename T>
	class SList
	{
	public:
		typedef SListItem<T> LItem;
	public:
		SList() { root = 0; end = 0; }
		SList(LItem* Item) { 
			root = Item;
			if (root)
			{
				end = root;
				while (end->Next())
				{
					end = end->Next();
				}
			}
		}
	public:
		LItem* Root() { return root; };
		LItem* Root(LItem* Item) {return root = Item;}
	public:
		virtual void AddItem(LItem* Item)
		{
			if (Item)
			{
				if (end)
				{
					end->Next(Item);
					end = Item;
				}
				else
				{
					root = end = Item;
				}
			}
		}
	protected:
		LItem* root;
		LItem* end;
	};

	template<typename T>
	class RSList :public SList<T>
	{
	public:
		RSList():SList<T>::SList() { }
		RSList(SList<T>::LItem* Item):SList<T>::SList(Item){
			if (SList<T>::root)
			{
				if (SList<T>::end)
				{
					SList<T>::end->Next(SList<T>::root);
				}
			}
		}
	public:
		virtual void AddItem(SList<T>::LItem* Item)
		{
			SList<T>::AddItem(Item);
			if (SList<T>::end)
			{
				SList<T>::end->Next(SList<T>::root);
			}
		}
	public:

	};
}

#endif // !SPTADT_H